#pragma once

#include "common.h"

HelperLibBegin

#include <vector>
using std::vector;
#include <algorithm>

template<typename T, bool is_minimum = true>
class binary_heap
{
public:
  binary_heap(int init_capacity = 100)
    :data_(init_capacity)
  {

  }

  template<typename Iterable>
  binary_heap(Iterable &&items)
    : ele_count_(std::size(items))
    , data_(ele_count_ * 2 + 2)
  {
    int index = 0;
    for (auto &t : items) {
      data_[index++] = t;
    }

    build_heap();
  }

  ~binary_heap() = default;

  bool empty() const { return ele_count_ == 0; }

  size_t size() const { return ele_count_; }

  const T & front() const
  {
    if (empty()) {
      throw std::runtime_error{ "binery_heap is empty" };
    }

    return data_[0];
  }

  void push(T const& x)
  {
    if (ele_count_ == data_.size()) {
      data_.resize(ele_count_ * 2 + 2);
    }

    data_[ele_count_] = x;
    percolate_up(ele_count_++);
  }

  void pop()
  {
    if (empty()) {
      throw std::runtime_error{ "binery_heap is empty" };
    }

    data_[0] = data_[ele_count_-- - 1];
    if (!empty())percolate_down(0);
  }

  void for_each(std::function<void(T const&)> func)
  {
    for (int i = 0; i < ele_count_; i++)func(data_[i]);
  }

private:

  void percolate_down(int hole)
  {
    if (hole < 0 || hole >= ele_count_) throw std::runtime_error{ "index out of range" };

    T val = data_[hole];
    int child_index = hole * 2 + 1;
    while (child_index < ele_count_) {
      int higher_index = (child_index + 1 == ele_count_ || higher_compare(data_[child_index], data_[child_index + 1]))
        ? child_index : child_index + 1;
      if (higher_compare(val, data_[higher_index])) break;
      data_[hole] = data_[higher_index];
      hole = higher_index;
      child_index = hole * 2 + 1;
    }
    data_[hole] = val;
  }

  void percolate_up(int hole)
  {
    if (hole < 0 || hole >= ele_count_) throw std::runtime_error{ "index out of range" };

    int parent_index = (hole - 1) / 2;
    T val = data_[hole];
    while (hole > 0) {
      if (higher_compare(data_[parent_index], val))break;
      data_[hole] = data_[parent_index];
      hole = parent_index;
      parent_index = (hole - 1) / 2;
    }
    data_[hole] = val;
  }

  inline bool higher_compare(T const&left, T const&right)
  {
    if (is_minimum) return left < right;
    return left > right;
  }

  void build_heap()
  {
    for (int i = ele_count_ / 2; i >= 0; i--) {
      percolate_down(i);
    }
  }
private:
  int ele_count_{ 0 };
  vector<T> data_;
};

HelperLibEnd
